import java.util.*;

public class TopKclass {
    public List<String> topKFrequent(String[] words, int k){
        Map<String,Integer> map=new HashMap<>();
        //1.统计每个单词出现的次数map
        for (String s:words) {
            if(map.get(s)==null){
                map.put(s,1);
            }else {
                int val=map.get(s);
                map.put(s,val+1);
            }
        }
        //2.建立一个大小为K的小根堆
        PriorityQueue<Map.Entry<String,Integer>> minHeap=new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue())==0){
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue()-o2.getValue();
            }
        });
        //3.遍历Map
        for(Map.Entry<String,Integer> entry:map.entrySet()){
            if(minHeap.size()<k){
                minHeap.offer(entry);
            }else {
                //说明堆中已经放满了k个元素，需要看堆顶元素的数据和当前的数据的大小关系
                Map.Entry<String,Integer> top=minHeap.peek();
                //判断频率是否相同，如果相同，比较单词的大小，单词小入堆
                if(top.getValue().compareTo(entry.getValue())==0){
                    if(top.getKey().compareTo(entry.getKey())>0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }else {
                    if(top.getValue().compareTo(entry.getValue())<0){
                        minHeap.poll();
                        minHeap.offer(entry);
                    }
                }
            }
        }
        List<String> ret=new ArrayList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> top=minHeap.poll();
            ret.add(top.getKey());

        }
        Collections.reverse(ret);
        return ret;
    }
}
